\documentclass{amsart}
%=================================================================
% general packages
\usepackage{graphicx,color}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath, amssymb}
\usepackage{eqnarray}
\usepackage{breqn}
\usepackage{multirow}
\usepackage{subfig}
\usepackage{cite}

%=================================================================
\begin{document}

%=================================================================
%
\title[Circle Detection]{Report on Circle Detection and Registration}%

\author{Tianlong Yun}
\address[A.~1]{CATR, 40th Xueyuan Road \\
Beijing, P.R.China}%
\email[A.~1]{yuntianlong2002@gmail.com}

\maketitle
\tableofcontents


%=================================================================

\section{Summary}\label{sec-intro}
Detection and registration have become a critical issue for medical
image processing. \emph{SIFT} and \emph{SURF} are among the typical
ones. In this report, I provide the solution to the problem by using
$OpenCV$ 2.3.1. For the first problem, I get the location and the
contour information of all the circles first. Then, zero-order and
first-order moments are used to calculate the coordinate of center
point. The radius of each point is obtained by getting the area of
the contours. For the second problem, I sort the data obtained in
problem 1 by the radius, then choose three points in the data set of
figure A with the smallest size. Then I search their corresponding
$image$ points in the data set of figure B. The reason why I sort
the data first is because the similarity transformation did change
the size of the circles(But measurement error may exist). So we only
need to search the circles in figure B with the approximately same
size as the selected three points in figure A. The time complexity
of this algorithm is $O(x^3)$ but not $O(n^3)$, x refer to the
number of the smallest circles in the figure pair. This is a
reasonable time complexity because x usually only account for 5-10
percentage of all the circles. For problem 3, I divided the data set
pair into different cluster, in each cluster, three points in figure
A and three points in B will be selected to check if they are
matched in term of the similarity transformation every round. If the
threshold is well defined, only one cluster will be checked and we
can get the matched points and parameter. This algorithm cost more
time than the one in problem 2, but it is robust. The experiment
also show that my solution have a reasonable performance on these
problem. The rest of the report is organized as follows. In
Sec.~\ref{sec-preliminaries}, I will provide the approach to
configure the developing environment as well as build the project
and run the application followed by the proposed algorithm and
complexity analysis in Sec.~\ref{sec-method}. In
Sec.~\ref{sec-experiment}, I provide the experimental analysis.

\section{Preliminaries} \label{sec-preliminaries}

\subsection{Developing Environment}The Developing Environment is as follow:\\
OS: Microsoft Windows XP Professional Version 2002 Service Pack 3\\
IDE: Microsoft Visual C++ 2008 Express Edition with SP1\\
Dependency: OpenCV2.3.1
\subsection{Configuration of OpenCV}OpenCV installing file is a executable file. In the following part, we assume we install
it in \emph{F:$\backslash$Program Files$\backslash$OpenCV2.3.1.}

Put\\
\emph{F:$\backslash$Program
Files$\backslash$OpenCV2.3.1$\backslash$build$\backslash$common$\backslash$tbb$\backslash$ia32$\backslash$vc9\\}
\emph{F:$\backslash$Program
Files$\backslash$OpenCV2.3.1$\backslash$build$\backslash$x86$\backslash$vc9$\backslash$bin\\}
into environment variable $PATH$.

Open Visual C++ and Select ``Tools''-``Options''-``Projects and
Solutions''-``VC++ Directories'', and add the
following directories\\
\emph{F:$\backslash$Program
Files$\backslash$OpenCV2.3.1$\backslash$build$\backslash$include\\}
\emph{F:$\backslash$Program
Files$\backslash$OpenCV2.3.1$\backslash$build$\backslash$include$\backslash$opencv\\}
\emph{F:$\backslash$Program
Files$\backslash$OpenCV2.3.1$\backslash$build$\backslash$include$\backslash$opencv2\\}
into ``Include Files'' and add the following directory\\
\emph{D:$\backslash$Program
Files$\backslash$OpenCV2.3.1$\backslash$build$\backslash$x86$\backslash$vc9$\backslash$lib}
into ``Library Files''

Right click the project in the ``Solution Explorer'' ,and Select
``Properties''-``Linker''-``Input'', and add the libraries in
$release.txt$ into ``Additional Dependencies''(\emph{Configuration:
Release}) and add the libraries in $debug.txt$ into ``Additional
Dependencies''(\emph{Configuration: Debug}).

\subsection{Compile and Build the Solution}
I didn't create a single project for problem 1 because the two other
projects have already finish the task of problem 1.

\subsection{Solution Structure}Brief description of the files in the
solution.\\
\emph{utils.h},\emph{utils.cpp}:Miscellaneous utility functions.\\
\emph{detection.h},\emph{detection.cpp}:Functions for detecting and matching circles\\
\emph{Program1and2.cpp}:Main program for program 1 and 2\\
\emph{Program1and3.cpp}:Main program for program 1 and 3\\
\emph{readme.txt}:Contain the structure of solution and the usage of the executable file\\
\emph{debug.txt}:Contain the libraries needed in $Debug mode$\\
\emph{release.txt}:Contain the libraries needed in $Release mode$\\
\emph{result}:Contain all the testing result\\
\emph{Report.pdf}:This document\\
\subsection{Testing}

The executable file can be found in \emph{$\backslash$Circle
Detection and Registration$\backslash$Release} or
\emph{$\backslash$Circle Detection and
Registration$\backslash$Debug}. Put figure A as the first parameter
and figure B as the second. $>$ is used to capture the output data.
For example, \emph{Problem1and3 figureA.bmp figureB.bmp $>$
data.txt}.

\section{Method} \label{sec-method}
\subsection{Program 1}
In OpenCV, $HoughCircles$ method is widely used in the detection of
circles. However, this algorithm is not applicable in this problem.
$HoughCircles$ focus on the macroscopic feature of the whole image
while the smaller circles are often ignored. For example, a
circle(in red color)in Fig.~\ref{fig:HoughCircles} might be detected
because a bunch of smaller circles present feature of a circle.

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=0.55\textwidth]{HoughCircles.jpg}\\
  \caption {HoughCircles}
  \label{fig:HoughCircles}
\end{center}
\end{figure}

Then the $OpenCV$ function $cvFindContours$ is used to solve the
problem. Because these figures are monochrome bitmap, it is easy to
find the contours of all the circle. The area of each circle can be
obtained directly with $OpenCV$ function $cvContourArea$, so the
radius can be calculated as well. However, the the center
coordinates of a circle is relatively hard to get. Noting that the
function $cvMoments$ can return the moments of a points set, we can
calculate the center coordinates using the spatial moment(denoted as
$M_{xy}$, x and y are the order of x and y respectively). The
coordinates center point of circle can then be calculated in this
way:

\begin{equation}
centerx=M_{10}/M_{00}
\end{equation}
\begin{equation}
centery=M_{01}/M_{00}
\end{equation}

Also, the $>$ in Windows command line is used to avoid the
programming with file writing.

\subsection{Program 2}
The second problem is to calculate the parameter according ot the
point set. The transformation can be denoted as:

\begin{equation}
[
  \begin{array}{c}
    x_1 \\
    y_1 \\
  \end{array}
]=s\left(
  \begin{array}{cc}
    cos(\alpha) & -sin(\alpha) \\
    sin(\alpha) & cos(\alpha) \\
  \end{array}
  \right)[\begin{array}{c}
           x_0 \\
           y_0
         \end{array}
         ]+[
                         \begin{array}{c}
                           u \\
                           v \\
                         \end{array}
                       ]
\end{equation}

This is an affine transformation. To get s, a, u, and v, the rigid
transformation parameters, we must find three pairs(not in the same
line) of corresponding points. However, finding which points in
figure B is the $image$ of the ones in figure A is not a trivial
work. So, the radius of these points is being taken into
consideration.

The similarity transformation basically didn't change the size of
each circle. So we sort the result by the radius. The circles with
approximately same size are matched with each other. Noting that the
number of this kind of of circle pair are usually more than three.
So we must search for the right ones.

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=0.55\textwidth]{pair.jpg}\\
  \caption {The progress to find the paired circles}
\end{center}
\end{figure}

Based on the properties of affine transformation, if three points
form a triangle in figure A, the transformation didn't change the
angle or the proportion between two line segment. If we can find a
pair of similar triangles, the parameter can be determine.(This
method may reach a wrong result especially there plenty of points)

After finding such triangle pair, the vertexes with same angle are
matched. In order to reduce the computational cost, we use \emph{Law
of Sines} to improve the calculation.

\begin{equation}
a/Sin(A)=b/Sin(B)=c/Sin(C)=k
\end{equation}
\begin{equation}
a/b=Sin(A)/Sin(B)
\end{equation}
\begin{equation}
b/c=Sin(B)/Sin(C)
\end{equation}
\begin{equation}
 a/c=Sin(A)/Sin(C)
\end{equation}

Assuming that the three vertexes in figure A are denoted as $A$,$B$
and $C$ and in figure B are $A'$,$B'$ and $C'$ respectively. And the
sides of the triangle are $a$, $b$, $c$ and $a'$, $b'$, $c'$. If we
get $a$/$b$=$a'$/c'$, $a$/$c$=$a'$/b$ and $b$/$c$=$c'$/$b'$, we can
get the correct relationship ($A,A'$),($B,C'$) and ($C,B'$) which
showed in Fig.~\ref{fig:Sine}.

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=0.55\textwidth]{sine.jpg}\\
  \caption {Obtain matched points using Law of Sines}
  \label {fig:Sine}
\end{center}
\end{figure}

After obtaining the three pairs of points, we can use the $OpenCV$
function $cvGetAffineTransform$ to calculate the affine parameter.

\begin{algorithm}
\caption{Matching algorithm for image with no error} \label{alg-r1}
\begin{algorithmic}
 \STATE \textbf{Primilinaries} : \\\hspace{4mm}$M$: the number of circles in figure A;
 \\\hspace{4mm}$N$: the number of circles in figure B;
  \\\hspace{4mm}$A_i$: Circle center points in figure A $i(i=1,...,M)$;
 \\\hspace{4mm}$B_i$: Circle center points in figure B $i(i=1,...,N)$;
\FOR {each three points in figure B with approximately size with
$A_1$ $A_2$ $A_3$}
    \IF {$B_x$ $B_y$ $B_z$ are matched with $A_1$ $A_2$ $A_3$}     \STATE Find three sets of matched points;
    \ELSE
    \STATE one of x,y or z will increase by one
    \ENDIF
\ENDFOR \STATE No matched points are found, the threshold should
increase;
     \STATE \textbf{end}
\end{algorithmic}
\end{algorithm}

Because all the points in figure A have a image in figure B, we
choose $A_1$ $A_2$ $A_3$ as the $preimage$ while search for all
possible in figure B. Actually, only small proportion of points in
figure B have to be searched because the data has been sorted. If
the radius of $A_1$ $A_2$ $A_3$ is small, the radius of their image
in figure B will be small too and the result can be found in a few
rounds.

\subsubsection{Time complexity}
The time complexity of this algorithm is largely depended on the
characteristic of the figure. In term of this problem, the radius of
all the circles in one figure can be divided in serval groups, so
there may be more than one ``smallest radius''. Assuming there are
$X$ smallest radius ($X>3$). The time complexity inn the worst
situation is $C^3_x$ which means the time complexity is about
$O(x^3)$.

\subsection{Program 3}
The algorithm for problem 3 is inspired by the one for problem 2. In
problem 3, a circle in one image may not exist in the other image,
so we can not simply select the three first points as the
$preimage$. However, a overall correspondence exists which can be
denoted in Fig.~\ref{fig:Bar}

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=0.55\textwidth]{bar.jpg}\\
  \caption {Common continuous section between two figure}
  \label {fig:Bar}
\end{center}
\end{figure}

If we can find a common continuous section between the two figure,
then we can search the matched points in the section. The algorithm
for problem 3 is almost the same as the last one. However, their
should be a loop for getting the \emph{three points} in figure A.

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=0.55\textwidth]{trans.jpg}\\
  \caption {The progress to find the paired circles}
\end{center}
\end{figure}

\subsubsection{Time complexity}
The time complexity of this algorithm is relatively large. At the
worst situation, it can be $O(x^6)$ and x refers to the length of a
common continuous section. But we must notice that a common
continuous section is usually quite short. This algorithm can work
efficiently in the situation of this problem.

\section{Experiment and Analysis} \label{sec-experiment}
\subsection{Program 1}
The program works well in all the images. Here is a comparison
between the original image and the retrieval using the output
information of program show in Fig.~\ref{fig:comp}.

\begin{figure}[ht]
\begin{center}
    \centerline{\includegraphics[width=0.5\textwidth]{figurea.jpg}\includegraphics[width=0.5\textwidth]{retrieval.eps}}
    \caption {Comparison Between Original Image and the Retrieved Image}
    \label{fig:comp}
\end{center}
\end{figure}

\subsection{Program 2 and 3}

These two program work well as showed in the \emph{Result} folder.

\newpage
\end{document}
